package com.leetCode;

import java.util.ArrayList;
import java.util.List;

public class _17_22_GenerateParentheses {

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        dg(0, 0, n, new StringBuilder(), result);
        return result;
    }

    private static void dg(int left, int right, int n, StringBuilder sb, List<String> result) {
        if (left == n && right == n) {
            result.add(sb.toString());
            return;
        }
        if (left < n)
            dg(left + 1, right, n, new StringBuilder(sb.append('(')), result);
        if (right < n && right < left)
            dg(left, right + 1, n, new StringBuilder(sb.append(')')), result);
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

}
